

// function quickSort(arr) {
//     if (arr.length <= 1) {
//         return arr;
//     }
//     var middleIndex = Math.floor(arr.length / 2);
//     var left = [];
//     var right = [];
//     var middle = arr.splice(middleIndex, 1)[0];
//     for (var i = 0; i < arr.length; i++) {
//         if (arr[i] > middle) {
//             right.push(arr[i]);
//         } else {
//             left.push(arr[i]);
//         }
//     }
//     return quickSort(left).concat(middle, quickSort(right));
// }

function quickSort(arr) {
    if (arr.length < 1) {
        return arr
    }
    let middleIndex = Math.floor(arr.length / 2)
    let left = [];
    let right = [];
    console.log(arr, middleIndex)
    // let middle = arr[middleIndex]
    let middle = arr.splice(middleIndex, 1)[0]
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < middle) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    return quickSort(left).concat([middle], quickSort(right))
}

console.log(quickSort([1, 9, 2, 4, 7, 4, 6]))



// function swap(A, i, j) {
//     const t = A[i];
//     A[i] = A[j];
//     A[j] = t;
// }


// function divide(A, p, r) {
//     const x = A[r - 1];
//     let i = p - 1;
//     for (let j = p; j < r - 1; j++) {
//         if (A[j] <= x) {
//             i++;
//             swap(A, i, j);
//         }
//     }
//     swap(A, i + 1, r - 1);
//     return i + 1;
// }

// function qsort(A, p = 0, r) {
//     r = r || A.length;
//     if (p < r - 1) {
//         const q = divide(A, p, r);
//         qsort(A, p, q);
//         qsort(A, q + 1, r);
//     }
//     return A;
// }